home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 3 / Info_Mac_1994-01.iso / Development / Source / MultiSession 1.04 Source / Core 27⁄June⁄1993 / CSack.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-15  |  15.8 KB  |  496 lines  |  [TEXT/KAHL]
  1. /* CSack.c */
  2.  
  3. #include "CSack.h"
  4. #include "Memory.h"
  5.  
  6.  
  7. void                CSack::PushElement(void* Element)
  8.     {
  9.         SackBlock**            Temp;
  10.         register short    Scan;
  11.  
  12.         ERROR(Initialized != True,PRERR(ForceAbort,
  13.             "CSack::PushElement called on uninitialized object."));
  14.         EXECUTE(Scannable = False;)
  15.         CheckHandleExistence((Handle)FirstBlock);
  16.         if (((**FirstBlock).NumBytes) < MaxBytesPerBlock)
  17.             {
  18.                 Temp = (SackBlock**)AllocHandle(((**FirstBlock).NumBytes
  19.                     + BytesPerElement) + sizeof(SackBlock));
  20.                 SetTag(Temp,"CSack Block");
  21.                 (**Temp).Next = (**FirstBlock).Next;
  22.                 (**Temp).NumElements = (**FirstBlock).NumElements + 1;
  23.                 (**Temp).NumBytes = (**FirstBlock).NumBytes + BytesPerElement;
  24.                 ERROR((**Temp).NumBytes % BytesPerElement != 0,PRERR(ForceAbort,
  25.                     "CSack::PushElement element array size inconsistency"));
  26.                 HRNGCHK(Temp,&((**Temp).Data[BytesPerElement]),(**FirstBlock).NumBytes);
  27.                 HRNGCHK(FirstBlock,&((**FirstBlock).Data[0]),(**FirstBlock).NumBytes);
  28.                 MemCpy(&((**Temp).Data[BytesPerElement]),&((**FirstBlock).Data[0]),
  29.                     (**FirstBlock).NumBytes);
  30.                 HRNGCHK(Temp,&((**Temp).Data[0]),BytesPerElement);
  31.                 MemCpy(&((**Temp).Data[0]),Element,BytesPerElement);
  32.                 ReleaseHandle((Handle)FirstBlock);
  33.                 FirstBlock = Temp;
  34.             }
  35.          else
  36.             {
  37.                 Temp = (SackBlock**)AllocHandle(sizeof(SackBlock) + BytesPerElement);
  38.                 SetTag(Temp,"CSack Block");
  39.                 (**Temp).Next = FirstBlock;
  40.                 (**Temp).NumElements = 1;
  41.                 (**Temp).NumBytes = BytesPerElement;
  42.                 HRNGCHK(Temp,&((**Temp).Data[0]),BytesPerElement);
  43.                 MemCpy(&((**Temp).Data[0]),Element,BytesPerElement);
  44.                 FirstBlock = Temp;
  45.             }
  46.     }
  47.  
  48.  
  49. MyBoolean        CSack::KillElement(void* Element)
  50.     {
  51.         SackBlock**            Scan;
  52.         SackBlock**            Lag;
  53.         register short    Index;
  54.  
  55.         ERROR(Initialized != True,PRERR(ForceAbort,
  56.             "CSack::KillElement called on uninitialized object."));
  57.         EXECUTE(Scannable = False;)
  58.         Scan = FirstBlock;
  59.         Lag = NIL;
  60.         while (Scan != NIL)
  61.             {
  62.                 CheckHandleExistence((Handle)Scan);
  63.                 for (Index = 0; Index < (**Scan).NumBytes; Index += BytesPerElement)
  64.                     {
  65.                         HRNGCHK(Scan,&((**Scan).Data[Index]),BytesPerElement);
  66.                         if (MemEqu(Element,&((**Scan).Data[Index]),BytesPerElement))
  67.                             {
  68.                                 SackBlock**            Temp;
  69.                                 register short    Count;
  70.  
  71.                                 Temp = (SackBlock**)AllocHandle((**Scan).NumBytes
  72.                                     - BytesPerElement + sizeof(SackBlock));
  73.                                 SetTag(Temp,"CSack Block");
  74.                                 (**Temp).Next = (**Scan).Next;
  75.                                 (**Temp).NumElements = (**Scan).NumElements - 1;
  76.                                 (**Temp).NumBytes = (**Scan).NumBytes - BytesPerElement;
  77.                                 HRNGCHK(Temp,&((**Temp).Data[0]),Index);
  78.                                 HRNGCHK(Scan,&((**Scan).Data[0]),Index);
  79.                                 MemCpy(&((**Temp).Data[0]),&((**Scan).Data[0]),Index);
  80.                                 HRNGCHK(Temp,&((**Temp).Data[Index]),(**Scan).NumBytes
  81.                                     - BytesPerElement - Index);
  82.                                 HRNGCHK(Scan,&((**Scan).Data[Index + BytesPerElement]),
  83.                                     (**Scan).NumBytes - BytesPerElement - Index);
  84.                                 MemCpy(&((**Temp).Data[Index]),&((**Scan).Data[Index + BytesPerElement]),
  85.                                     (**Scan).NumBytes - BytesPerElement - Index);
  86.                                 if (Lag == NIL)
  87.                                     {
  88.                                         FirstBlock = Temp;
  89.                                     }
  90.                                  else
  91.                                     {
  92.                                         CheckHandleExistence((Handle)Lag);
  93.                                         (**Lag).Next = Temp;
  94.                                     }
  95.                                 ERROR((**Temp).NumBytes % BytesPerElement != 0,PRERR(ForceAbort,
  96.                                     "CSack::KillElement element array size inconsistency"));
  97.                                 ReleaseHandle((Handle)Scan);
  98.                                 if (((**Temp).NumElements == 0) && (Temp != FirstBlock))
  99.                                     {
  100.                                         (**Lag).Next = (**Temp).Next;
  101.                                         ReleaseHandle((Handle)Temp);
  102.                                     }
  103.                                 return True; /* return after deletion of one */
  104.                             }
  105.                     }
  106.                 Lag = Scan;
  107.                 Scan = (**Scan).Next;
  108.             }
  109.         return False;
  110.     }
  111.  
  112.  
  113. void                CSack::ResetScan(void)
  114.     {
  115.         ERROR(Initialized != True,PRERR(ForceAbort,
  116.             "CSack::ResetScan called on uninitialized object."));
  117.         NextHandleToAccess = FirstBlock;
  118.         NextIndexToAccess = -BytesPerElement; /* start out one before */
  119.         EXECUTE(Scannable = True;)
  120.     }
  121.  
  122.  
  123. MyBoolean        CSack::GetNext(void* PlaceToPut)
  124.     {
  125.         register short        Scan;
  126.  
  127.         ERROR(Initialized != True,PRERR(ForceAbort,
  128.             "CSack::GetNext called on uninitialized object."));
  129.         ERROR(!Scannable,PRERR(ForceAbort,
  130.             "CSack::GetNext called on unscannable object."));
  131.      RestartPoint:
  132.         if (NextHandleToAccess == NIL)
  133.             {
  134.                 return False;
  135.             }
  136.         CheckHandleExistence((Handle)NextHandleToAccess);
  137.         ERROR(NextIndexToAccess % BytesPerElement != 0,PRERR(ForceAbort,
  138.             "CSack::GetNext NextIndexToAccess inconsistency"));
  139.         ERROR((**NextHandleToAccess).NumBytes % BytesPerElement != 0,PRERR(ForceAbort,
  140.             "CSack::GetNext element array size inconsistency"));
  141.         NextIndexToAccess += BytesPerElement;
  142.         if (NextIndexToAccess >= (**NextHandleToAccess).NumBytes)
  143.             {
  144.                 NextHandleToAccess = (**NextHandleToAccess).Next;
  145.                 NextIndexToAccess = -BytesPerElement;
  146.                 goto RestartPoint;
  147.             }
  148.         HRNGCHK(NextHandleToAccess,&((**NextHandleToAccess).Data[NextIndexToAccess]),
  149.             BytesPerElement);
  150.         MemCpy(PlaceToPut,&((**NextHandleToAccess).Data[NextIndexToAccess]),BytesPerElement);
  151.         return True;
  152.     }
  153.  
  154.  
  155. ulong                CSack::NumElements(void)
  156.     {
  157.         register ulong                Accr;
  158.         register SackBlock**    Scan;
  159.  
  160.         ERROR(Initialized != True,PRERR(ForceAbort,
  161.             "CSack::NumElements called on uninitialized object."));
  162.         Accr = 0;
  163.         Scan = FirstBlock;
  164.         while (Scan != NIL)
  165.             {
  166.                 CheckHandleExistence((Handle)Scan);
  167.                 ERROR((**Scan).NumBytes % BytesPerElement != 0,PRERR(ForceAbort,
  168.                     "CSack::GetNext element array size inconsistency"));
  169.                 Accr += (**Scan).NumElements;
  170.                 Scan = (**Scan).Next;
  171.             }
  172.         return Accr;
  173.     }
  174.  
  175.  
  176. /* */                CSack::CSack()
  177.     {
  178.         SackBlock**            Shadow;
  179.  
  180.         SetTag(this,"CSack");
  181.         Shadow = (SackBlock**)AllocHandle(sizeof(SackBlock));
  182.         SetTag(Shadow,"CSack Block");
  183.         (**Shadow).Next = NIL;
  184.         (**Shadow).NumElements = 0;
  185.         (**Shadow).NumBytes = 0;
  186.         FirstBlock = Shadow;
  187.         EXECUTE(Scannable = False;)
  188.     }
  189.  
  190.  
  191. /* */                CSack::~CSack()
  192.     {
  193.         register SackBlock**    FirstImage;
  194.         register SackBlock**    Temp;
  195.  
  196.         ERROR(Initialized != True,PRERR(ForceAbort,
  197.             "CSack::~CSack called on uninitialized object."));
  198.         FirstImage = FirstBlock;
  199.         while (FirstImage != NIL)
  200.             {
  201.                 Temp = FirstImage;
  202.                 FirstImage = (**FirstImage).Next;
  203.                 ReleaseHandle((Handle)Temp);
  204.             }
  205.     }
  206.  
  207.  
  208. void                CSack::ISack(long TheSizeOfElement, long TheMaxElementsPerBlock)
  209.     {
  210.         ERROR(Initialized == True,PRERR(ForceAbort,
  211.             "CSack::ISack called on already initialized object."));
  212.         EXECUTE(Initialized = True);
  213.         BytesPerElement = TheSizeOfElement;
  214.         MaxBytesPerBlock = TheMaxElementsPerBlock * TheSizeOfElement;
  215.         ERROR((BytesPerElement<0)||(BytesPerElement>32767),PRERR(ForceAbort,
  216.             "CSack::ISack BytesPerElement initializer is out of range."));
  217.         ERROR((MaxBytesPerBlock<BytesPerElement)||(MaxBytesPerBlock>32767),PRERR(ForceAbort,
  218.             "CSack::ISack MaxBytesPerBlock initializer is out of range."));
  219.         EXECUTE(MaxBytesPerBlock = TheSizeOfElement * 4;) /* for error testing */
  220.     }
  221.  
  222.  
  223. MyBoolean        CSack::GetCurrent(void* PlaceToPut)
  224.     {
  225.         register short        Scan;
  226.  
  227.         ERROR(Initialized != True,PRERR(ForceAbort,
  228.             "CSack::GetCurrent called on uninitialized object."));
  229.         ERROR(!Scannable,PRERR(ForceAbort,
  230.             "CSack::GetCurrent called on unscannable object."));
  231.      RestartPoint:
  232.         if ((NextHandleToAccess == NIL) || (NextIndexToAccess < 0))
  233.             {
  234.                 return False;
  235.             }
  236.         HRNGCHK(NextHandleToAccess,&((**NextHandleToAccess).Data[NextIndexToAccess]),
  237.             BytesPerElement);
  238.         MemCpy(PlaceToPut,&((**NextHandleToAccess).Data[NextIndexToAccess]),BytesPerElement);
  239.         return True;
  240.     }
  241.  
  242.  
  243. MyBoolean        CSack::AdvanceToNext(void)
  244.     {
  245.         ERROR(Initialized != True,PRERR(ForceAbort,
  246.             "CSack::AdvanceToNext called on uninitialized object."));
  247.         ERROR(!Scannable,PRERR(ForceAbort,
  248.             "CSack::AdvanceToNext called on unscannable object."));
  249.      RestartPoint:
  250.         if (NextHandleToAccess == NIL)
  251.             {
  252.                 return False;
  253.             }
  254.         NextIndexToAccess += BytesPerElement;
  255.         if (NextIndexToAccess >= (**NextHandleToAccess).NumBytes)
  256.             {
  257.                 NextHandleToAccess = (**NextHandleToAccess).Next;
  258.                 NextIndexToAccess = 0;
  259.                 goto RestartPoint;
  260.             }
  261.         return True;
  262.     }
  263.  
  264.  
  265. /* insert after any that return negative or zero number, but before one that */
  266. /* returns a positive number (post-insertion sort) which allows us to use this */
  267. /* to implement a stable sort. */
  268. void                CSack::InsertSorted(void* Element, short (*Comparator)(void*,void*))
  269.     {
  270.         SackBlock**        SackScan;
  271.         SackBlock**        Lag;
  272.         SackBlock**        LookAhead;
  273.         long                    Index;
  274.         SackBlock**        Temp;
  275.         long                    Count;
  276.  
  277.         ERROR(Initialized != True,PRERR(ForceAbort,
  278.             "CSack::InsertSorted called on uninitialized object."));
  279.         EXECUTE(Scannable = False;)
  280.         /* First, find which block it should be inserted into. */
  281.      RetryPoint:
  282.         SackScan = FirstBlock;
  283.         if (SackScan == NIL)
  284.             {
  285.                 /* use the normal routine to add an element to an empty list */
  286.                 PushElement(Element);
  287.                 return;
  288.             }
  289.         Lag = NIL;
  290.         LookAhead = (**SackScan).Next;
  291.         while ((LookAhead != NIL) && (HLock((Handle)LookAhead),
  292.             (*Comparator)(Element,&((**LookAhead).Data[0])) >= 0))
  293.             {
  294.                 HUnlock((Handle)LookAhead);
  295.                 Lag = SackScan;
  296.                 SackScan = LookAhead;
  297.                 LookAhead = (**SackScan).Next;
  298.             }
  299.         if (LookAhead != NIL) {HUnlock((Handle)LookAhead);}
  300.         /* if the block is too big, we have to break it into two. */
  301.         if ((**SackScan).NumBytes + BytesPerElement >= MaxBytesPerBlock)
  302.             {
  303.                 SackBlock**        FirstHalf;
  304.                 SackBlock**        SecondHalf;
  305.                 long                    ElementsInFirstHalf;
  306.                 long                    ElementsInSecondHalf;
  307.                 long                    Scan;
  308.  
  309.                 ElementsInFirstHalf = (**SackScan).NumElements / 2;
  310.                 ElementsInSecondHalf = (**SackScan).NumElements - ElementsInFirstHalf;
  311.                 FirstHalf = (SackBlock**)AllocHandle(sizeof(SackBlock)
  312.                     + (ElementsInFirstHalf * BytesPerElement));
  313.                 SetTag(FirstHalf,"CSack Block");
  314.                 SecondHalf = (SackBlock**)AllocHandle(sizeof(SackBlock)
  315.                     + (ElementsInSecondHalf * BytesPerElement));
  316.                 SetTag(SecondHalf,"CSack Block");
  317.                 if (Lag == NIL)
  318.                     {
  319.                         FirstBlock = FirstHalf;
  320.                     }
  321.                  else
  322.                     {
  323.                         (**Lag).Next = FirstHalf;
  324.                     }
  325.                 (**FirstHalf).Next = SecondHalf;
  326.                 (**FirstHalf).NumElements = ElementsInFirstHalf;
  327.                 (**FirstHalf).NumBytes = ElementsInFirstHalf * BytesPerElement;
  328.                 (**SecondHalf).Next = (**SackScan).Next;
  329.                 (**SecondHalf).NumElements = ElementsInSecondHalf;
  330.                 (**SecondHalf).NumBytes = ElementsInSecondHalf * BytesPerElement;
  331.                 HRNGCHK(FirstHalf,&((**FirstHalf).Data[0]),(**FirstHalf).NumBytes);
  332.                 HRNGCHK(SackScan,&((**SackScan).Data[0]),(**FirstHalf).NumBytes);
  333.                 MemCpy(&((**FirstHalf).Data[0]),&((**SackScan).Data[0]),(**FirstHalf).NumBytes);
  334.                 HRNGCHK(SecondHalf,&((**SecondHalf).Data[0]),(**SecondHalf).NumBytes);
  335.                 HRNGCHK(SackScan,&((**SackScan).Data[(**FirstHalf).NumBytes]),
  336.                     (**SecondHalf).NumBytes);
  337.                 MemCpy(&((**SecondHalf).Data[0]),&((**SackScan).Data[(**FirstHalf).NumBytes]),
  338.                     (**SecondHalf).NumBytes);
  339.                 ReleaseHandle((Handle)SackScan);
  340.                 /* go back and make sure we are still inserting into proper block */
  341.                 goto RetryPoint;
  342.             }
  343.         /* Now we have the block (SackScan) so where to insert into it? */
  344.         HLock((Handle)SackScan);
  345.         Index = 0;
  346.         /* We can only insert in the <Index> position if the element before */
  347.         /* us is less than or equal to us and the element after us is greater */
  348.         /* than us.  If Index == 0, then there is no element before us. */
  349.         /* The first scan works so that we won't ever insert before the first */
  350.         /* element (it stops before the first element is equal to or greater than */
  351.         /* us).  Thus, we check the one that will be after us and advance until it is */
  352.         /* greater.  If we hit the end, we append. */
  353.         while ((Index < (**SackScan).NumBytes) && ((*Comparator)(Element,
  354.             &((**SackScan).Data[Index])) >= 0))
  355.             {
  356.                 /* Scanning... */
  357.                 Index += BytesPerElement;
  358.             }
  359.         HUnlock((Handle)SackScan);
  360.         /* if (Index == NumBytes), then we append, else we insert */
  361.         /* the algorithm is the same for either one... */
  362.         Temp = (SackBlock**)AllocHandle(HandleSize((Handle)SackScan) + BytesPerElement);
  363.         SetTag(Temp,"CSack Block");
  364.         (**Temp).Next = (**SackScan).Next;
  365.         (**Temp).NumElements = (**SackScan).NumElements + 1;
  366.         (**Temp).NumBytes = (**SackScan).NumBytes + BytesPerElement;
  367.         if (Lag == NIL)
  368.             {
  369.                 FirstBlock = Temp;
  370.             }
  371.          else
  372.             {
  373.                 (**Lag).Next = Temp;
  374.             }
  375.         /* copying over preceding zone */
  376.         HRNGCHK(Temp,&((**Temp).Data[0]),Index);
  377.         HRNGCHK(SackScan,&((**SackScan).Data[0]),Index);
  378.         MemCpy(&((**Temp).Data[0]),&((**SackScan).Data[0]),Index);
  379.         /* copying over element */
  380.         HRNGCHK(Temp,&((**Temp).Data[Index]),BytesPerElement);
  381.         MemCpy(&((**Temp).Data[Index]),Element,BytesPerElement);
  382.         /* copying over succeeding range (does nothing if Index == NumLongs) */
  383.         HRNGCHK(Temp,&((**Temp).Data[Index + BytesPerElement]),(**SackScan).NumBytes - Index);
  384.         HRNGCHK(SackScan,&((**SackScan).Data[Index]),(**SackScan).NumBytes - Index);
  385.         MemCpy(&((**Temp).Data[Index + BytesPerElement]),&((**SackScan).Data[Index]),
  386.             (**SackScan).NumBytes - Index);
  387.         ReleaseHandle((Handle)SackScan);
  388.     }
  389.  
  390.  
  391. void                CSack::KillCurrent(void)
  392.     {
  393.         SackBlock**            Scan;
  394.         SackBlock**            Lag;
  395.         SackBlock**            Temp;
  396.         register short    Count;
  397.  
  398.         ERROR(Initialized != True,PRERR(ForceAbort,
  399.             "CSack::KillElement called on uninitialized object."));
  400.         ERROR(!Scannable,PRERR(ForceAbort,
  401.             "CSack::KillCurrent called on unscannable object."));
  402.         /* this function preserves scannability */
  403.         if ((NextIndexToAccess < 0) || (NextHandleToAccess == NIL))
  404.             {
  405.                 return; /* couldn't do it */
  406.             }
  407.         Scan = FirstBlock;
  408.         Lag = NIL;
  409.         while (Scan != NextHandleToAccess)
  410.             {
  411.                 Lag = Scan;
  412.                 Scan = (**Scan).Next;
  413.             }
  414.         ERROR(Scan == NIL,PRERR(ForceAbort,"CSack internal list inconsistency"));
  415.         Temp = (SackBlock**)AllocHandle((**Scan).NumBytes - BytesPerElement + sizeof(SackBlock));
  416.         SetTag(Temp,"CSack Block");
  417.         (**Temp).Next = (**Scan).Next;
  418.         (**Temp).NumElements = (**Scan).NumElements - 1;
  419.         (**Temp).NumBytes = (**Scan).NumBytes - BytesPerElement;
  420.         HRNGCHK(Temp,&((**Temp).Data[0]),NextIndexToAccess);
  421.         HRNGCHK(Scan,&((**Scan).Data[0]),NextIndexToAccess);
  422.         MemCpy(&((**Temp).Data[0]),&((**Scan).Data[0]),NextIndexToAccess);
  423.         HRNGCHK(Temp,&((**Temp).Data[NextIndexToAccess]),
  424.             (**Scan).NumBytes - BytesPerElement - NextIndexToAccess);
  425.         HRNGCHK(Scan,&((**Scan).Data[NextIndexToAccess + BytesPerElement]),
  426.             (**Scan).NumBytes - BytesPerElement - NextIndexToAccess);
  427.         MemCpy(&((**Temp).Data[NextIndexToAccess]),&((**Scan).Data[NextIndexToAccess
  428.             + BytesPerElement]),(**Scan).NumBytes - BytesPerElement - NextIndexToAccess);
  429.         if (Lag == NIL)
  430.             {
  431.                 FirstBlock = Temp;
  432.             }
  433.          else
  434.             {
  435.                 CheckHandleExistence((Handle)Lag);
  436.                 (**Lag).Next = Temp;
  437.             }
  438.         ReleaseHandle((Handle)Scan);
  439.         if (((**Temp).NumElements == 0) && (Temp != FirstBlock))
  440.             {
  441.                 (**Lag).Next = (**Temp).Next;
  442.                 ReleaseHandle((Handle)Temp);
  443.                 Temp = (**Lag).Next;
  444.             }
  445.         NextHandleToAccess = Temp;
  446.         /* now check to see if that was the last in handle, and if so, advance to next */
  447.      RestartPoint:
  448.         if (NextIndexToAccess >= (**NextHandleToAccess).NumBytes)
  449.             {
  450.                 NextHandleToAccess = (**NextHandleToAccess).Next;
  451.                 NextIndexToAccess = 0;
  452.             }
  453.         return;
  454.     }
  455.  
  456.  
  457. /* write data to the node currently being accessed */
  458. MyBoolean        CSack::RewriteCurrent(void* PlaceToGet)
  459.     {
  460.         register short        Scan;
  461.  
  462.         ERROR(Initialized != True,PRERR(ForceAbort,
  463.             "CSack::RewriteCurrent called on uninitialized object."));
  464.         ERROR(!Scannable,PRERR(ForceAbort,
  465.             "CSack::RewriteCurrent called on unscannable object."));
  466.      RestartPoint:
  467.         if ((NextHandleToAccess == NIL) || (NextIndexToAccess < 0))
  468.             {
  469.                 return False;
  470.             }
  471.         HRNGCHK(NextHandleToAccess,&((**NextHandleToAccess).Data[NextIndexToAccess]),
  472.             BytesPerElement);
  473.         MemCpy(&((**NextHandleToAccess).Data[NextIndexToAccess]),PlaceToGet,BytesPerElement);
  474.         return True;
  475.     }
  476.  
  477.  
  478. MyBoolean        CSack::DoesItContain(void* Element)
  479.     {
  480.         Handle        DataTemp;
  481.  
  482.         DataTemp = AllocHandle(BytesPerElement);
  483.         HLock(DataTemp);
  484.         ResetScan();
  485.         while (GetNext(*DataTemp))
  486.             {
  487.                 if (MemEqu(*DataTemp,Element,BytesPerElement) == 0)
  488.                     {
  489.                         ReleaseHandle(DataTemp);
  490.                         return True;
  491.                     }
  492.             }
  493.         ReleaseHandle(DataTemp);
  494.         return False;
  495.     }
  496.